package com.captain.leetcode2.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.List;
import java.util.Objects;

/**
 * 给你单链表的头指针 head 和两个整数 left 和 right ，
 * 其中 left <= right 。请你反转从位置 left
 * 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class 反转链表II92 {
    public static void main(String[] args) {
        new 反转链表II92().reverseBetween2(ListNode.getInstance(), 1, 4);
        //new 反转链表II92().revers(ListNode.getInstance());

    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) return null;
        if (left == right) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        int indexLeft = 1;
        int indexRight = 1;
        ListNode pre = new ListNode(-1);
        ListNode back = new ListNode(-1);
        ListNode tp = new ListNode(-1);
        while (cur.next != null) {
            if (indexLeft == left) {
                tp = cur.next;
                cur.next = null;
                pre = dummy.next;
                cur = tp;
                indexLeft++;
                indexRight++;
                continue;
            }
            //处理右节点
            if (indexRight == right) {
                //1,2,
                back = cur.next.next;
                cur.next.next = null;
                break;
            }
            indexLeft++;
            indexRight++;
            cur = cur.next;

        }
        ListNode revers = revers(tp);
        if (pre == null) {
            dummy.next = revers;
        } else {
            dummy.next = pre;
            while (pre.next != null) {
                pre = pre.next;
            }
            pre.next = revers;
        }
        while (revers.next != null) {
            revers = revers.next;
        }
        revers.next = back;
        return dummy.next;
    }

    /**
     * des:
     *
     * @return {@link ListNode }
     * @author captain
     * @date 2021/9/3 8:56
     */
    public ListNode reverseBetween2(ListNode head, int left, int right) {
        if (head == null) return null;
        if (left == right) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode pre = new ListNode(-1);
        ListNode tp = new ListNode(-1);
        ListNode back = new ListNode(-1);
        int indexLeft = 1;
        int indexRight = 1;
        while (cur.next != null) {
            //0 1 2 3 4 5 找到前指針，中, 后
            if (indexLeft == left) {
                tp = cur.next;
                cur.next = null;
                pre = dummy.next;
                cur = tp;
                indexLeft++;
                indexRight++;
                continue;
            }
            if (indexRight == right) {
                back = cur.next.next;
                cur.next.next = null;
                break;
            }
            indexLeft++;
            indexRight++;
            cur = cur.next;
        }
        //拼接链表
        ListNode revers = revers(tp);
        //当 left = 1 时 , pre链表为空, 需要特殊处理
        if (pre == null) {
            dummy.next = revers;
        } else {
            dummy.next = pre;
            pre = getLastNode(pre);
            pre.next = revers;
        }
        revers = getLastNode(revers);
        revers.next = back;
        return dummy.next;
    }

    /**
     * des: 获取最后的节点
     *
     * @author captain
     */
    public ListNode getLastNode(ListNode head) {
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }

    /**
     * @param head 待反转链表
     */
    public ListNode revers(ListNode head) {
        ListNode pre = null;
        // -1 2 3 4
        while (head != null) {
            ListNode tp = head.next;
            head.next = pre;
            pre = head;
            head = tp;
        }
        return pre;
    }
}
